home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 6314 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.8 KB
  1. Path: csd.uwo.ca!jamie
  2. From: jamie@csd.uwo.ca (J. Blustein)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: unique id for a string
  5. Date: 23 Feb 1996 20:55:27 GMT
  6. Organization: Computer Science Dept., Univ. of Western Ontario, London, Canada
  7. Message-ID: <4gl9jv$9f2@falcon.ccs.uwo.ca>
  8. References: <1996Feb16.175601.114182@kuhub.cc.ukans.edu> <3129dd39.961626@news.iquest.net> <4gfpveINNe68@keats.ugrad.cs.ubc.ca> <4gih8a$b62@madeline.ins.cwru.edu>
  9. Reply-To: jamie@uwo.ca
  10. NNTP-Posting-Host: mccarthy.csd.uwo.ca
  11. Summary: Referecne of TCJ article about fast find for min. perfect hash functions
  12. Keywords: hash minimal perfect finding reference journal
  13. X-Copyright: copyright (c) J. Blustein, 1996.  All rights reserved 
  14. Disclaimer: It's people like you what cause unrest!
  15.  
  16. In article <4gih8a$b62@madeline.ins.cwru.edu>,
  17. >Actually, it's not *that* difficult to find.  Try running gperf from GNU
  18. >or reading the paper cited in my previous post in this subject.  The
  19. >results in the paper claim to be able to find a perfect hash function
  20. >for 262,144 18-character words in 16.087 seconds on a Sun Sparc 2.
  21. >Doesn't sound that difficult to me.  :)
  22.  
  23.     I was looking through back issues of TCJ just yesterday and so I happen
  24. to have this reference beside me.  I haven't read the article but I think
  25. it will help:
  26.  
  27.     A Linear Time Algorithm for Finding Minimal Perfect Hash Functions
  28.     Zbigniew J. Czech and Bohdan S. Majewski
  29.     The Computer Journal 36(6), 1993
  30.     I don't know the page numbers.
  31.  
  32.     If you want something that is already implemented (a different sort of
  33. time complexity) then gperf might be just the ticket.  I think it's neat
  34. myself.
  35. -- 
  36. Jamie Blustein                                         `Did you say "knives"?'
  37. <jamie@uwo.ca>                                         `*Rotating* knives, yes.'
  38.